package io.zouyalong.algo.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/insert-interval/
 */
public class InsertInterval {

    public int[][] solution(int[][] intervals, int[] newInterval) {
        var result = new LinkedList<int[]>();
        int i = 0;
        for (; i < intervals.length && intervals[i][1] < newInterval[0]; i++) {
            result.add(intervals[i]);
        }
        int start = newInterval[0];
        if (i < intervals.length && intervals[i][0] < start) {
            start = intervals[i][0];
        }
        int end = newInterval[1];
        for (; i < intervals.length && intervals[i][1] < end; i++);
        if (i < intervals.length) {
            if (intervals[i][0] <= end) {
                end = intervals[i][1];
                i++;
            }
        }
        result.add(new int[]{start, end});
        for (; i < intervals.length; i++) {
            result.add(intervals[i]);
        }
        return result.toArray(new int[result.size()][]);
    }

    public static void main(String[] args) {
        var input = new int[][]{
                new int[]{1, 3},
                new int[]{4, 5},
                new int[]{6, 7},
        };
        var interval = new int[]{1, 8};
        var inst = new InsertInterval();
        var result = inst.solution(input, interval);
        for (int[] each:result) {
            System.out.printf("%s", Arrays.toString(each));
        }
//        System.out.printf("result: %s", Arrays.toString(result));
    }
}
